package com.lhcai.lc.category.doublepointer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 15. 三数之和
 *
 * @author liuhuaicai
 * @since 2024-10-13 12:03
 */
public class Lc15 {
    public static void main(String[] args) {
        Lc15 lc15 = new Lc15();
        List<List<Integer>> lists = lc15.threeSum(new int[]{-1, 0, 1, 2, -1, -4});
        System.out.println(lists);
    }

    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        // 枚举 a
        for (int i = 0; i < n; i++) {
            // 去除重复的,需要和上一次枚举的数不相同
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            //  c 对应的指针初始指向数组的最右端
            int k = n - 1;
            int target = -nums[i];
            // 枚举 j
            for (int j = i + 1; j < n; j++) {
                // 需要和上一次枚举的数不相同
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                // 需要保证b 的指针在 c的指针的左侧
                while (j < k && nums[j] + nums[k] > target) {
                    k--;
                }
                // 如果指针重合，随着 b 后续的增加
                // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                if (j == k) {
                    break;
                }
                // 发现符合条件的
                if (nums[j] + nums[k] == target) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(nums[k]);
                    res.add(list);
                }
            }
        }
        return res;
    }

    /**
     * 将三数之和理解为两数之和 ， 使用三重for循环
     * 超出时间限制
     * 308 / 313 个通过的测试用例
     *
     * @param nums nums
     * @return List<List < Integer>>
     */
//    public List<List<Integer>> threeSum(int[] nums) {
//        // i,j,k互不相等，且nums[i] + nums[j] + nums[k] == 0
//        List<List<Integer>> threeList = new ArrayList<>();
//        // 目标是 三数之和等于0，可以理解为两数之和为另一数的负数
//        for (int i = 0; i < nums.length; i++) {
//            for (int j = i + 1; j < nums.length; j++) {
//                int num = nums[i] + nums[j];
//                for (int k = 0; k < nums.length; k++) {
//                    if (num == -nums[k] && k != i && k != j) {
//                        List<Integer> list = Arrays.asList(nums[i], nums[j], nums[k]);
//                        Collections.sort(list);
//                        threeList.add(list);
//                    }
//                }
//            }
//        }
//        List<List<Integer>> res = threeList.stream().distinct().collect(Collectors.toList());
//        return res;
//    }
}
